perm filename 4.2[0,BGB] blob
sn#075337 filedate 1974-02-14 generic text, type C, neo UTF8
COMMENT ā VALID 00006 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 6.2 Three image formats: Video, CRE and FEV.
C00006 00003 KINDS OF CRE NODES.
C00011 00004 CRE LINK AND DATUM NAMES.
C00014 00005 CRE RINGS, TREES, LISTS AND ARRAYS.
C00017 00006
C00021 ENDMK
Cā;
6.2 Three image formats: Video, CRE and FEV.
DATA STRUCTURE: BASICS.
The two generic data structures of CRE are arrays and nodes;
there are five kinds of arrays and eight kinds of nodes.
The node
structures is implemented as seven word fixed sized
blocks. The data structure in CRE represents a sequence in
time of video intensity contour maps. Such contour maps are like
topographical elevation contour maps, in that no two contour lines
should ever cross and in that all the contour lines should close.
Consequently, the loops of contours enclose regions; and these
regions overlap in a nested fashion forming a tree like data
structure.
As the general examples of contoured images on page 5
illustrate, a notion that is emphatically not in CRE, is that of a
schematic line drawing. Although the CRE output can be viewed as a
collection of lines on a display screen, people expecting a line
drawing rendition of the given television picture will be
disappointed. A CRE picture is a simple transformation of the
photometry, geometry and topology of the original video image;
whereas the typical line drawing from a human illustrator is a
representation of the scene without photometric information. On the
other hand, the work of an artist such as Peter Max; or a
paint-by-the-numbers grid does resembly CRE output. This is not an
idle coincidance but rather a consequence of whether or not the
artist is trying to represent photometric data by quantum lines.
The explanation of CRE node structures will be presented in
three parts: first, the several kinds of nodes will be briefly
explained; second, the sub structures such as rings, trees and
lists will be discribed; and third, the node formats and their
contents will be explained in detail.
KINDS OF CRE NODES.
The are eight kinds of CRE nodes: Vector, Arc, Polygon,
Shape, Image, Level, Film and Empty.
1. At the very top of all the structure is the film node, the film
node is unique and serves as an OBLIST from which all other nodes
may be reached. The film node embodies the idea of a piece of
celluloid film or a length of magnetic video tape. A film is a
sequence of images taken by the same camera of the same scene with
only a small amount of action between images.
2. An image node represents the familiar two dimensional idea of a
photograph or an oil painting or to be exact a digital video image
of 216 rows by 288 columns of numbers ranging from 0 for dark to 63
for bright. The image is formed by a thin lens and is projected on
a flat image plane. The idea of an image is so common that it is
easy to overlook the wonder of sun light scattering off of surfaces,
refracting thru a lens, and forming a complex pattern called a real
image.
3. Below the image node are the intensity contour levels. A contour
level is a binary image that results from thresholding a gray scaled
image. So an image is composed of levels, and in turn, a level is
composed of polygons.
4. A Polygon node represents the idea of a contour loop which
always closes upon itself and does not cross itself or any other
contour. Contour loops are approximated by a ring of vectors; hence,
the term "polygon". The contour polygons always have at least three
sides and are simply connected.
5. Shape nodes contain data about one or two polygons. The data in a
shape node is not a positive representation of the notion of shape;
but is rather the parameters of allignment and normalization that
must be compensated before shapes can be compared.
6. Vector nodes contain the locus of an image vertex; however since
vectors always belong to a polygon and always have two neighbors;
their counterclockwise neighbor is considered to determine their
vector direction.
7. Arc nodes are vectors that are made by the polygon smoothing
routine; one arc typically replace several vectors. When both arcs
and vectors are being discussed; vectors are strictly horizontal and
vertical, whereas arcs may point in any direction.
8. Empty nodes are an artifact of the fixed node size dynamic
storage allocation mechanism used in CRE. Entities are made by
taking empty nodes from an AVAIL list and entities are killed by
returning their node to the AVAIL list; there is no garbage
collector, but there is a space compactor.
CRE LINK AND DATUM NAMES.
Nodes contain either numerical data or pointers to other
nodes; such node pointers are actual machine addresses and are
called links. The positions within a node where a link is stored are
named and are reserved for particular uses. In the table below the
11 link names and 13 datum names are introduced. The link names
will always appear capitalized.
11 LINK NAMES:
CW clockwise
CCW counter clockwise
DAD parent of node up a tree structure.
SON descendent of a node down a tree structure.
ENDO Greek for inside, polygon within.
EXO Greek for outside, surrounding polygon.
ALT alternate.
NGON negative polygon.
PGON positive polygon.
NTIME negative in real time, into the past.
PTIME positive in real time, into the future.
13 DATUM NAMES:
Boolean datums.
type type of node bits.
reloc rellocation of node bits.
Fixed point datums.
row row of image locus.
col column of image locus.
cntrst contrast of an edge, vector and arc.
ncnt number count, various uses.
Floating point datums.
zdepth z depth from camera lens center.
perm length of perimeter.
area area in pixel units.
mxx moment of inertia about X axis.
myy moment of inertia about Y axis.
mzz moment of inertia about Z axis.
pxy product of inertia with respect
to the X and Y axes.
CRE RINGS, TREES, LISTS AND ARRAYS.
CRE inputs an image into an array called TVBUF; it makes the
node structures, some of which are temporary; and it outputs a final
version of the structure representing a film of images. The
temporary structures are relevant to understanding the process; but
only the final structure is relevant to using CRE output. In
summary, the important structures are:
FOUR RINGS.
1. Image ring of the film.
2. Level ring of an image.
3. Polygon ring of a level.
4. Vector ring of a polygon.
TWO TREES.
1. The tree of rings.
2. The tree of nested polygons.
TWO LISTS.
1. Time line lists.
2. The empty node list.
TEMPORARY STRUCTURES.
1. Arc rings of polygons.
2. Fusion shape rings of levels.
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
There is one film node. The film is composed of a ring of
images. Each image is composed of a ring of levels. Each level is
composed of a ring of polygons. Each polygon is composed of a ring
of vectors. The ring structures are implemented with the four links
named DAD, SON, CW and CCW. The rings are headless only in the
sense that all the elements of a ring are brothers; a pointer to the
head of a ring is stored in the DAD link of each element. The DAD of
the film node is NIL; and NIL is an 18-bit zero. The final SON of
all vector nodes is also NIL. The DAD and SON links form a tree of
rings.
Besides the tree of rings, there is the tree of nested
polygons. The nested polygon tree is implemented with the four
links named ENDO, EXO, NGON and PGON. The EXO of a polygon points
at its surronding polygon. The ENDO of a polygon points at one of
the polygons that may be enclaved within the given polygon; and the
NGON and PGON links form a ring of polygons that have the same EXO
polygon.
The time line lists run thru arc and polygon nodes. In the
simple case, the time line links of a polygon point to a
corresponding polygon in the image previous (NTIME) or subsequent
(PTIME) of the current polygon. The correspondence being that the
time polygon is exactly the same intensity at nearly the same
location, orientation, and size as the given polygon. In the case of
polygon fusion, the time line link of a polygon points to a time
polygon of which the given polygon becomes a part. In the case of
polygon fission, the time line link of a polygon points to only one
the pieces into which the given polygon splits.
The time line links of an arc vector point to a
corresponding arc vector in the image previous or subsequent of the
current arc vector. The polygons of arc vectors mated in time are
also mated in time; because after polygon time line links have been
made, one polygon is temporarily translated, rotated and dilated so
as to have the same lamina inertia tensor as its mate; that is the
locus of the arc vectors of one polygon are temporarily altered;
then the corresponding arc vectors are found and their time line
linkages are made.
The empty node list is maintained in the CCW link positions;
the last empty node contains a zero link. All nodes are explicitly
made from and killed to the empty node list by the subroutines
MKNODE and KLNODE.
The arc ring of a polygon is just like a vector ring except
that the pointer to it is stored in the ALT link of the polygon,
while the polygon has both a ring of vectors and a ring of arcs.
The fusion shape ring of a intensity level runs thru the CW
and CCW links of shape nodes and is pointed at by the ALT link of
the level. Fusion shape nodes are the shapes generated to represent
pairs of polygons unmated in time.